6263. Башня карликов

 

Маленький Вася играет в игру “Башня карликов”. В этой игре имеются n различных предметов, которые Вы можете дать персонажу – карлику. Предметы пронумерованы от 1 до n. Вася хочет получить предмет номер 1.

Имеются два варианта получения предметов:

·        Вы можете купить предмет. i-ый предмет стоит ci денег.

·        Вы можете сконструировать предмет. В игре имеется возможность сделать только m типов предметов. Для получения нового предмета Вам следует отдать два различных предмета.

Помогите Васе потратить наименьшее количество денег для приобретения предмета номер 1.

 

Вход. Первая строка содержит два числа n и m (1 ≤ n ≤ 10000, 0 ≤ m ≤ 100000) – количество различных предметов и число конструирований.

Вторая строка содержит n целых чисел ci (0 ≤ ci ≤ 109) – стоимости предметов.

Следующие m строк описывают преобразования предметов, каждая строка содержит три различных целых числа ai, xi, yi, где ai предмет, который можно сконструировать из xi и yi (1 ≤ ai, xi, yi ≤ n, ai ≠ xi, xi ≠ yi, yi ≠ ai).

 

Выход.  Выведите одно число – наименьшее количество потраченных денег.

 

Пример входа 1

Пример выхода 1

5 3

5 0 1 2 5

5 2 3

4 2 3

1 4 5

2

 

 

Пример входа 2

Пример выхода 2

3 1

2 2 1

1 2 3

2

 

 

РЕШЕНИЕ

жадность

 

Анализ алгоритма

Построим граф – список смежности g, где g[i] содержит пары чисел (j, a) такие что из предметов i и j можно сконструировать предмет a: (i, j) → a.

Пусть cost – массив, изначально содержащий стоимость покупки предметов (cost[i] = ci). В конце алгоритма cost[i] будет содержать наименьшее количество денег, за которое можно получить предмет i.

 

Изначально все предметы являются необработанными (used[i] = 0).

Пока существует хотя бы один необрабротанный предмет

·                   Находим предмет a с наименьшей стоимостью;

·                   Применяем все правила, перечисленные в g[a];

·                   Отмечаем предмет a обработанным: used[a] = 0;

 

Для каждого правила (a, b) → to из g[a] пересчитываем

cost[to] = min(cost[to], cost[a] + cost[b])

 

Пример

Рассмотрим первый тест. Имеются 5 предметов со следующими стоимостями их покупки:

Имеются три правила конструирования предметов. Построим из них список смежности.

Предмет 2 имеет наименьшую стоимость cost[2] = 0. Применяем правила, в которых задействован предмет 2, а именно правила, перечисленные в g[2]. Отмечаем предмет 2 обработанным.

Следующим необработанным предметом с наименьшей стоимостью будет 3. Применяем правила, перечисленные в g[3]. Никакая из стоимостей не изменится.

Следующим необработанным предметом с наименьшей стоимостью будет 4. Применяем правило в g[4].

В следующих операциях стоимости предметов не изменятся. Таким образом стоимость получения предмета 1 равна 2.

 

Реализация алгоритма

Объявим рабочие массивы. Объявим список смежности g, содержащий правила конструирования предметов.

 

vector<int> cost, used;

vector<vector<pair<int, int>>> g;

 

Читаем входные данные. Инициализируем массивы.

 

scanf("%d %d", &n, &m);

g.resize(n + 1);

cost.resize(n + 1);

used.resize(n + 1);

 

Читаем стоимости покупки предметов.

 

for (i = 1; i <= n; i++)

  scanf("%d", &cost[i]);

 

Читаем правила конструирования предметов. Строим из них список смежности.

 

for (i = 0; i < m; i++)

{

  scanf("%d %d %d", &a, &x, &y);

  g[x].push_back(make_pair(y, a));

  g[y].push_back(make_pair(x, a));

}

 

Совершаем n итераций.

 

for (k = 0; k < n; k++)

{

 

Среди необработанных предметов ищем тот, который имеет наименьшую стоимость. Таким будет предмет номер a.

 

  mn = 2e9; a = -1;

  for (i = 1; i <= n; i++)

    if (!used[i] && cost[i] < mn)

    {

      mn = cost[i];

      a = i;

    }

 

Отмечаем предмет a обработанным.

 

  used[a] = 1;

 

Перебираем правила, в которых задействован предмет a.

 

      for (auto x : g[a])

      {

         b = x.first;

         to = x.second; // (a, b) -> to

         if (cost[a] + cost[b] < cost[to]) cost[to] = cost[a] + cost[b];

  }

}

 

Выводим наименьшее количество потраченных денег для покупки первого предмета.

 

printf("%d\n", cost[1]);

 

Реализация алгоритма

В Python inf представляет собой специальное значение, которое символизирует бесконечность. Это значение доступно в модуле math, и его следует импортировать.

 

from math import inf

 

Читаем входные данные.

 

n, m = map(int, input().split())

cost = [0] + list(map(int, input().split()))

 

Инициализируем списки.

 

used = [False] * (n + 1)

g = [[] for _ in range(n + 1)]

 

Читаем правила конструирования предметов. Строим из них список смежности.

 

for _ in range(m):

  a, x, y = map(int, input().split())

  g[x].append((y, a))

  g[y].append((x, a))

 

Совершаем n итераций.

 

for k in range(n):

 

Среди необработанных предметов ищем тот, который имеет наименьшую стоимость. Таким будет предмет номер a.

 

  mn = inf

  a = -1

  for i in range(1, n + 1):

    if not used[i] and cost[i] < mn:

      mn = cost[i]

      a = i

 

Отмечаем предмет a обработанным.

 

  used[a] = True

 

Перебираем правила, в которых задействован предмет a.

 

  for b, to in g[a]:

    if cost[a] + cost[b] < cost[to]:

       cost[to] = cost[a] + cost[b]

 

Выводим наименьшее количество потраченных денег для покупки первого предмета.

 

print(cost[1])